#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef unsigned long long ll;
ll sp[N<<2],sn[N<<2],tp[N<<2],tn[N<<2];
bool ed[N<<2];ll a[N],w[N];int n,cl,tt,c[N<<2];

void pushu(int p){
	c[p]=c[p*2]+c[p*2+1];
	sp[p]=sp[p*2]+sp[p*2+1];
	sn[p]=sn[p*2]+sn[p*2+1];
}

void pushd(int p){
	if(tp[p]!=0){
		sp[p*2]+=tp[p]*c[p*2];sp[p*2+1]+=tp[p]*c[p*2+1];
		tp[p*2]+=tp[p];tp[p*2+1]+=tp[p];tp[p]=0;
	}if(tn[p]!=0){
		sn[p*2]+=tn[p]*c[p*2];sn[p*2+1]+=tn[p]*c[p*2+1];
		tn[p*2]+=tn[p];tn[p*2+1]+=tn[p];tn[p]=0;
	}
} 

void pushp(int p){
	if(tp[p]!=0){
		sp[p*2]+=tp[p]*c[p*2];sp[p*2+1]+=tp[p]*c[p*2+1];
		tp[p*2]+=tp[p];tp[p*2+1]+=tp[p];tp[p]=0;
	}
}

void pushn(int p){
	if(tn[p]!=0){
		sn[p*2]+=tn[p]*c[p*2];sn[p*2+1]+=tn[p]*c[p*2+1];
		tn[p*2]+=tn[p];tn[p*2+1]+=tn[p];tn[p]=0;
	}
}

ll gt(int p,int t){//cout<<p<<" "<<t<<'\n';
	if(ed[p])return (!t?sp[p]:sn[p]);pushd(p);
	if(!t)return (c[p*2+1]?gt(p*2+1,t):gt(p*2,t));
	else return (c[p*2]?gt(p*2,t):gt(p*2+1,t));
}

void ch(int p,int l,int r,int x){
	if(l==r){
		if(c[p]){c[p]=sp[p]=sn[p]=0;tt=-1;return;}
		else{c[p]=1;int x;tt=1;
			x=p;while(x>1){if((x&1)&&c[x-1]){sp[p]=gt(x-1,0);break;}x/=2;}
			x=p;while(x>1){if((!(x&1))&&c[x+1]){sn[p]=gt(x+1,1);break;}x/=2;}return;
		}
	}int mid=(l+r)>>1;pushd(p);
	if(x<=mid)ch(p*2,l,mid,x);else ch(p*2+1,mid+1,r,x);pushu(p);
}

void ad(int p,int l,int r,int lx,int rx,ll v,int t){
	if(lx<=l&&r<=rx){
		if(!t)tp[p]+=v,sp[p]+=v*c[p];
		else tn[p]+=v,sn[p]+=v*c[p];return;
	}int mid=(l+r)>>1;pushd(p);
	if(lx<=mid)ad(p*2,l,mid,lx,rx,v,t);
	if(rx>mid)ad(p*2+1,mid+1,r,lx,rx,v,t);pushu(p);
}

ll ask(int p,int l,int r,int lx,int rx,int t){if(lx>rx||lx<1||rx<1)return 0;
	if(lx<=l&&r<=rx)return (!t?sp[p]:sn[p]);int mid=(l+r)>>1;ll res=0;pushd(p);
	if(lx<=mid)res+=ask(p*2,l,mid,lx,rx,t);if(rx>mid)res+=ask(p*2+1,mid+1,r,lx,rx,t);return res;
}

ll gpr(int p,int l,int r,int w){if(w>c[1]||w<1)return 0;
	if(l==r)return sp[p];int mid=(l+r)>>1;pushp(p);
	if(c[p*2]>=w)return gpr(p*2,l,mid,w);else return gpr(p*2+1,mid+1,r,w-c[p*2]);
}

ll gnx(int p,int l,int r,int w){if(w>c[1]||w<1)return 0;
	if(l==r)return sn[p];int mid=(l+r)>>1;pushn(p);
	if(c[p*2]>=w)return gnx(p*2,l,mid,w);else return gnx(p*2+1,mid+1,r,w-c[p*2]);
}

int gp(int p,int l,int r,int w){
	if(w>c[1]||w<1)return 0;if(l==r)return l;int mid=(l+r)>>1;pushd(p);
	if(c[p*2]>=w)return gp(p*2,l,mid,w);else return gp(p*2+1,mid+1,r,w-c[p*2]);
}

void init(int p,int l,int r){
	c[p]=sp[p]=sn[p]=tp[p]=tn[p]=0;
	if(l==r){ed[p]=1;return;}int mid=(l+r)>>1;
	init(p*2,l,mid),init(p*2+1,mid+1,r);
}

void print(int p,int l,int r){
	cout<<l<<" "<<r<<" "<<c[p]<<" "<<sp[p]<<" "<<sn[p]<<"\n";if(l==r)return;
	int mid=(l+r)>>1;pushd(p);print(p*2,l,mid),print(p*2+1,mid+1,r);
}

int main(){
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],w[i]=a[i];
	sort(w+1,w+n+1);cl=unique(w+1,w+n+1)-w-1;
	init(1,1,cl);int l,r,md,an,pl,pp,pq;ll ans;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(w+1,w+cl+1,a[i])-w;
		ch(1,1,cl,a[i]);ad(1,1,cl,a[i],cl,w[a[i]]*tt,0),ad(1,1,cl,1,a[i],w[a[i]]*tt,1);
		pl=(c[1]+1)/2;//cout<<pl<<" "<<gw(1,1,cl,pl,0)<<" "<<gw(1,1,cl,c[1]-pl+2,1)<<"\n";
		if(gpr(1,1,cl,pl)>gnx(1,1,cl,c[1]-pl+2)){cout<<sn[1]-sp[1]<<"\n";}
		else{l=1,r=pl,an=pl;ans=0;
			while(l<=r){md=(l+r)>>1;
				if(gpr(1,1,cl,md)<=gnx(1,1,cl,c[1]-md+2))
					an=md,r=md-1;else l=md+1;
			}an--;
			pp=gp(1,1,cl,an-1),pq=gp(1,1,cl,c[1]-an+2);//cout<<pp<<" "<<pq<<"\n";
			ans+=ask(1,1,cl,pq,cl,1)-ask(1,1,cl,1,pp,0)-gpr(1,1,cl,an);an=c[1]-an;
			pp=gp(1,1,cl,an+1),pq=gp(1,1,cl,c[1]-an);//cout<<pp<<" "<<pq<<"\n";
			ans+=ask(1,1,cl,1,pq,1)-ask(1,1,cl,pp,cl,0)+gnx(1,1,cl,c[1]-an+1);cout<<ans<<"\n";
		}//print(1,1,cl);
	}return 0;
}
